package 蓝桥.模拟赛;

import java.util.Random;
import java.util.Scanner;

public class Main9 {
    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int m = in.nextInt();
//        int[][] nums = new int[n][m];
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                nums[i][j] = in.nextInt();
//            }
//        }

        // 随机生成数据
        int m = 300, n = 300;
        int[][] nums = new int[n][m];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // -1000~1000
                nums[i][j] = random.nextInt(-1000, 1001);
            }
        }

        // 求矩阵子矩阵的最大和
        // 前缀和
        int[][] preSum = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + nums[i-1][j-1];
            }
        }
        int res = Integer.MIN_VALUE;
        // (i,j)为左上角，(k,l)为右下角
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = i+1; k <= n; k++) {
                    for (int l = j+1; l <= m; l++) {
                        if(k-i==l-j){
//                            System.out.println(i+" "+j+" "+k+" "+l);
                            // 只包含矩阵边上的元素
                            int temp = preSum[k][l] - preSum[i-1][l] - preSum[k][j-1] + preSum[i-1][j-1];
                            if(k-i>1&&l-j>1){
                                // 不包含矩阵内部的矩阵
                                temp-=preSum[k-1][l-1] - preSum[i][l-1] - preSum[k-1][j] + preSum[i][j];

                            }
//                            if(temp==5)
//                                System.out.println(i+" "+j+" "+k+" "+l);

                            res = Math.max(res, temp);

                        }
                    }
                }
            }
        }
        System.out.println(res);
    }
}
